3966. Ярый коллекционер бабочек

 

Как известно, Андрей Сергеевич – заядлый коллекционер бабочек. Его коллекция огромна: в ней собраны экспонаты со всего мира. Будем считать, что в мире существует 2 * 109 видов бабочек.

Чтобы не запутаться, Андрей Сергеевич присвоил каждому виду уникальный номер, начиная с единицы. Теперь он хочет выяснить, есть ли бабочка с номером k в его коллекции или же придётся приложить немало усилий и средств, чтобы её добыть.

 

Вход. В первой строке задано целое число n (1 ≤ n ≤ 105) – количество видов бабочек в коллекции Андрея Сергеевича.

Во второй строке следуют n различных целых чисел, отсортированных по возрастанию, – номера видов бабочек, имеющихся в коллекции.

В третьей строке указано число m (1 ≤ m ≤ 105) – количество видов бабочек, о которых Андрей Сергеевич хочет узнать, есть ли они у него.

В четвёртой строке содержатся m целых чисел – номера видов бабочек, которые необходимо проверить.

 

Выход. Выведите m строк. Для каждого запроса выведите “YES”, если бабочка с данным номером есть в коллекции, и “NO” – в противном случае.

 

Пример входа

Пример выхода

7

10 47 50 63 89 90 99

4

84 33 10 82

NO

NO

YES

NO

 

 

РЕШЕНИЕ

структуры данных – set

 

Анализ алгоритма

Номера видов бабочек в коллекции будем хранить во множестве s. Тогда проверка того, присутствует ли бабочка вида x у Андрея Сергеевича, сводится к проверке принадлежности числа x множеству s.

 

Реализация алгоритма

Все номера видов бабочек из коллекции сохраняем во множестве s.

 

set<int> s;

 

Читаем входные данные.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  s.insert(x);

}

 

Обрабатываем m запросов.

 

scanf("%d", &m);

for (i = 0; i < m; i++)

{

 

Проверяем, есть ли в коллекции бабочка вида x. Ответ будет утвердительным, если число x принадлежит множеству s.

 

  scanf("%d", &x);

  if (s.find(x) != s.end()) puts("YES");

  else puts("NO");

}

 

Python реализация

Читаем входные данные.

 

n = int(input())

lst = list(map(int,input().split()))

m = int(input())

q = list(map(int,input().split()))

 

Все номера видов бабочек из коллекции сохраняем во множестве s.

 

s = set(lst)

 

Обрабатываем m запросов.

 

for x in q:

 

Проверяем, есть ли в коллекции бабочка вида x. Ответ будет утвердительным, если число x принадлежит множеству s.

 

  if x in s:

    print("YES")

  else:

    print("NO")